#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

bool _139(string str, vector<string> wordDict)
{
    int n = str.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (size_t i = 1; i <= n; i++)
    {
        for (auto word : wordDict)
        {
            int length = word.size();
            if (i >= length && str.substr(i - length, i) == word)
                dp[i] = dp[i] || dp[i - length];
        }
    }
    return dp[n];
}

int main()
{
    cout << boolalpha << _139("leetcode", vector<string>{"leet", "code"}) << endl;
    return 0;
}